package cn.myworld.algorithm.linear;

import java.util.Iterator;

/**
 * 队列
 * @param <T>
 */
public class Queue<T> implements Iterable<T> {

    private Node head;

    private Node tail;

    private int N;

    private class Node {
        public T data;
        public Node next;

        public Node(T data, Node next) {
            this.data = data;
            this.next = next;
        }
    }

    public Queue() {
        this.head = new Node(null, null);
        this.tail = null;
        this.N = 0;
    }

    public boolean isEmpty() {
        return N == 0;
    }

    public int size() {
        return N;
    }

    // 入队 （尾插法）
    public void enqueue(T e) {

        // tail为null
        if (tail == null) {
            tail = new Node(e, null);
            head.next = tail;
        } else {
            // tail不为null
            Node oldTail = tail;
            tail = new Node(e, null);
            oldTail.next = tail;
        }
        // 元素个数+1
        N++;
    }

    // 出队
    public T dequeue() {
        if (isEmpty()) {
            return null;
        }
        Node oldFirst = head.next;
        head.next = oldFirst.next;
        N--;

        // 因为出队列是在删除元素，如果在队列中的元素删除完了，需要重置tail为null
        if (isEmpty()) {
            tail = null;
        }

        return oldFirst.data;
    }

    @Override
    public Iterator<T> iterator() {
        return new QIterator();
    }

    private class QIterator implements Iterator<T> {

        private Node current;
        public QIterator() {
            this.current = head;
        }

        @Override
        public boolean hasNext() {
            return current.next != null;
        }

        @Override
        public T next() {
            current = current.next;
            return current.data;
        }
    }
}
